package com.example.arithmeticleetcode.leetcode.nov;

/**
 * @program: arithmetic-leetcode
 * @description:
 * @author: FangZhen
 * @create: 2020-11-09 09:36
 **/
public class Demo03 {

    public static void main(String[] args) {
        System.out.println(getMaximumGenerated(7));
        System.out.println(getMaximumGenerated(2));
        System.out.println(getMaximumGenerated(3));
        System.out.println(getMaximumGenerated(0));
        System.out.println(getMaximumGenerated(15)); // 5
    }


    public static int getMaximumGenerated(int n) {
        if (n == 0) {
            return 0;
        }
        if (n < 3) {
            return 1;
        }
        int[] nums = new int[n + 1];
        nums[0] = 0;
        nums[1] = 1;
        int i = 1;
        int count = 2;
        while (true) {
            if (count < nums.length) {
                nums[i << 1] = nums[i];
                count++;
            } else {
                break;
            }
            if (count < nums.length) {
                nums[(i << 1) + 1] = nums[i] + nums[i + 1];
                count++;
            } else {
                break;
            }
            i++;
        }
        int max = Integer.MIN_VALUE;
        for (int num : nums) {
            if (max < num) {
                max = num;
            }
        }
        return max;
    }

//    nums[0] = 0
//    nums[1] = 1
//    nums[(1 * 2) = 2] = nums[1] = 1
//    nums[(1 * 2) + 1 = 3] = nums[1] + nums[2] = 1 + 1 = 2
//    nums[(2 * 2) = 4] = nums[2] = 1

//    nums[(2 * 2) + 1 = 5] = nums[2] + nums[3] = 1 + 2 = 3
//    nums[(3 * 2) = 6] = nums[3] = 2
//    nums[(3 * 2) + 1 = 7] = nums[3] + nums[4] = 2 + 1 = 3
}
